package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2024. 考试的最大困扰度
 *
 * 一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。
 * （也就是连续出现 true 或者连续出现 false）。
 * 给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：
 * 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。
 * 请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。
 *
 * 示例 1：
 * 输入：answerKey = "TTFF", k = 2
 * 输出：4
 * 解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
 * 总共有四个连续的 'T' 。
 *
 * 示例 2：
 * 输入：answerKey = "TFFT", k = 1
 * 输出：3
 * 解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
 * 或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
 * 两种情况下，都有三个连续的 'F' 。
 *
 * 示例 3：
 * 输入：answerKey = "TTFTTFTT", k = 1
 * 输出：5
 * 解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
 * 或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
 * 两种情况下，都有五个连续的 'T' 。
 *
 * 提示：
 * n == answerKey.length
 * 1 <= n <= 5 * 10^4
 * answerKey[i] 要么是 'T' ，要么是 'F'
 * 1 <= k <= n
 *
 * <p>
 * User:Mr.Du
 * Date:2024/4/1
 * Time:14:38
 */
public class MaxConsecutiveAnswers {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        char[] chars = answerKey.toCharArray();
        return Math.max(get(chars, 'F', k), get(chars, 'T', k));
    }

    /**
     * 获取数组中满足条件的最长子数组的长度。
     * @param nums 由字符组成的数组
     * @param f 目标字符
     * @param k 需要目标字符出现的最小次数
     * @return 最长子数组的长度
     */
    public int get(char[] nums, char f, int k) {
        int n = nums.length; // 数组长度
        if(n == 1) return 1; // 数组只有一个元素时，直接返回1
        int r = 0, l = 0; // 右指针r和左指针l
        int res = 0, cnt = 0; // 最大子数组长度和当前目标字符计数
        while(r < n){ // 遍历数组
            if(nums[r] == f){ // 如果当前字符是目标字符
                cnt++; // 目标字符计数增加
            }
            while(cnt > k){ // 当目标字符计数大于k时，移动左指针l
                if(nums[l] == f){ // 如果左指针指向的是目标字符
                    cnt--; // 目标字符计数减少
                }
                l++; // 移动左指针
            }
            res = Math.max(res, r - l + 1); // 更新最大子数组长度
            r++; // 移动右指针
        }
        return res; // 返回最大子数组长度
    }

    /**
     * 计算在给定的答案键中，长度最多为k的连续相同答案的最大数量。
     *
     * @param answerKey 一个由答案字符组成的字符串，假设所有答案字符都是大写的字母'F'到'J'。
     * @param k 连续相同答案的最大长度限制。
     * @return 返回在answerKey中找到的连续相同答案的最大数量，满足最大长度不超过k的条件。
     */
    public int maxConsecutiveAnswers1(String answerKey, int k) {
        int ans = 0; // 存储最大连续相同答案数量
        int max = 0; // 辅助变量，存储当前连续相同答案的最大数量
        char[] str = answerKey.toCharArray(); // 将字符串转换为字符数组以方便操作
        int help[] = new int[26]; // 辅助数组，存储每个答案的出现频率
        int l = 0, r = 0, n = str.length; // l和r指针分别指向当前连续答案区间的左右端点，n为答案键的长度
        // 遍历答案键，更新连续相同答案的最大数量和区间长度
        while (r < n) {
            help[str[r] - 'F']++; // 当前答案的频率加一
            max = Math.max(max, help[str[r] - 'F']); // 更新当前最大频率
            r++; // 右指针向右移动
            // 当区间长度超过最大频率+k时，左指针向右移动并更新辅助数组
            while (r - l > max + k) {
                help[str[l] - 'F']--;
                l++;
            }
            ans = Math.max(ans, r - l); // 更新最大区间长度
        }
        return ans; // 返回最大连续相同答案的数量
    }
}
